package LeetCode1_100;

/**
 * 跳跃游戏 II
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。

 思路： 因为要按照最小步数达到最后一个位置， 就需要考虑数组长度，与数组中的元素概念，
 利用贪心思想，可以发现， 每一个位置上的数字i， 当前位置后面的 i位就是这个跳跃的最长点，遍历这个i位置，然后找出最大的值，然后再跳一下一次，

 直到到达数组末尾， 每次取最大值就行。  这道题容易进入一个思维误区， 老把跳跃次数与当前位置扯上关系，这样是不对的， 越想越乱，跳跃次数只与当前节点
 上所能到达的最远距离有关，  利用 双指针+贪心思想（每次选择最好），就可以写出代码。

 */
public class L_45 {
    public int jump(int[] nums) {
        int n = nums.length;
        int start =0;
        int end = 1;
        int ans =0;
        while (end<n){
            int max =0; // 每次拿到当前位置后面所能到达区域的最远长度
            for (int i = start; i <end ; i++) {
                max = Math.max(max,i+nums[i]);          // i+num[i] 当前位置上的元素能到达的最远距离
            }
            start = end;
            end = max+1;  // 下一次起跳的最远距离 ，遵循左开右闭原则
            ans++;
        }
        return ans;
    }
}
